/*
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/?envType=problem-list-v2&envId=array&
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：

输入：nums = [], target = 0
输出：[-1,-1]


分析： 先查找是否存在，再两次二分查找，一次查找左边界，一次查找右边界。
*/
#include<iostream>
#include<vector>

class Solution {
public:
    int bserach(std::vector<int>& nums,int left,int right,int target){  // 二分查找  
    
        while(left<=right){
            int mid = left + (right-left)/2;    // 不要写mid=(left+right)/2  这样有溢出的bug
            if(target==nums[mid]){
                return mid;
            }else if(target<nums[mid]){
                right = mid-1;
            }else {
                left = mid+1;
            }
        }
        return -1;
    }

    std::vector<int> searchRange(std::vector<int>& nums, int target) {
        int size = nums.size();
        int left = 0;
        int right = size -1;
        int left_mid = -1;
        int right_mid = -1;

        std::vector<int> ans;

        int mid = bserach(nums,left,right,target);
        if(-1==mid){                           // 二分查找是否存在
            ans.push_back(-1);
            ans.push_back(-1);
            return ans;
        }
        ans.push_back(mid);                    // 找到了
        ans.push_back(mid);

        left_mid = mid-1;
        right_mid = mid+1;
        
        while((left_mid>=left) && (bserach(nums,left,left_mid,target)!=-1)){   // 反复对左边范围进行查找，找到就是左边还有
            ans.at(0) = bserach(nums,left,left_mid,target);
            left_mid = left_mid -1;
        }
        while((right_mid<=right) && bserach(nums,right_mid,right,target)!=-1){ // 反复对右边范围进行查找，找到就是左边还有
            ans.at(1) = bserach(nums,right_mid,right,target);
            right_mid = right_mid +1;
        }

         return ans;
    }
};


int main (){ 
    std::vector<int> nums = {5,7,7,8,8,10};
    int target = 8;
    std::vector<int> ans;

    Solution leet =  Solution();
    ans = leet.searchRange(nums,target);
    for(auto i:ans){
        std::cout<<i<<std::endl;
    }

    return 0;
}